In our U.S. Pat. No. 6,971,084, there is described a multi-threaded processor which has several threads executing at the same time. These threads may be executed at different rates as the processor allocates more or less time to each one. There will in such a system be a plurality of data inputs, each supplying a pipeline of instructions for an execution thread. A control means routes the execution thread to an appropriate data processing means which is then caused to commence execution of the thread supplied to it. A determination is made repeatedly as to which routing operations and which execution threads are capable of being performed and subsequently at least one of the operations deemed capable of being performed is commenced. The system may be modified by including means for assigning priorities to threads so that execution of one or more threads can take precedence over other threads where appropriate resources are available.
Systems embodying the invention of U.S. Pat. No. 6,971,084 will typically have a number of threads executing at the same time on one or more different processors. The threads may be executed at different rates as the processors on which they are executing allocate more or less time to them in accordance with resource availability.
In some applications it is desirable to coordinate execution of two or more threads such that sections of their programs execute simultaneously (in synchronisation) for example to manage access to shared resources. This can be achieved by the utilisation of a synchronisation point provided in an execution thread which a processing means recognises as a point at which it may have to pause. Each free running thread will execute up to a synchronisation point and then pause. When all threads are paused at a synchronisation point they are synchronised and can be restarted simultaneously.
As with all software, the execution threads may have flow control branches and loops within them and it is therefore not always possible to predict which execution path a thread will take through a program. Therefore if one thread branches and thereby avoids a synchronisation point, a thread with which it is intended to be synchronised may be stalled indefinitely at a corresponding synchronisation point. As the first thread is not executing that section of the program it will never reach the relevant synchronisation point.
Alternatively, in such a situation, one thread which has branched to miss a first synchronisation point may unintentionally synchronise with a second thread at a second synchronisation point. For example, if the thread includes a branch point “if . . . end” branch which contains a synchronisation point A within it, and a synchronisation point B after it, then threads which do not skip the “if . . . end” branch would pause at the synchronisation point A within the branch and those that do skip it would pause at synchronisation point B after the branch.